﻿#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
		53,
			97,
			193,
			389,
			769,
			1543,
			3079,
			6151,
			12289,
			24593,
			49157,
			98317,
			196613,
			393241,
			786433,
			1572869,
			3145739,
			6291469,
			12582917, 25165843,
			50331653,
			100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

//
//// 请完成哈希表的如下操作
//// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
//模板特例化
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE

	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		typedef HashTable<K, V, Hash> hashtable;
		HashTable(int _size = 10)
		{
			_tables.resize(_size);
		}
		bool Insert(const pair<K, V>& kv) {
			int N = _n;
			int M = _tables.size();
			int fac = (N * 10) / M;
			if (fac>=7) {
				_tables.resize(__stl_next_prime(M + 1));
				hashtable tem(_tables.size());
				for (auto e : _tables) {
					if(e._state==EXIST) tem.Insert(e._kv);
				}
				_tables.swap(tem._tables);
				M = _tables.size();
			}
			Hash hash;
			int hash1 = hash(kv.first)% M;
			while (_tables[hash1]._state == EXIST) {
				if (hash1 == M - 1) hash1 = 0;
				else hash1++;
			}
			_n++;
			_tables[hash1]._kv = kv;
			_tables[hash1]._state = EXIST;
			return true;
		}
		HashData<K, V>* Find(const K& key) {
			int M = _tables.size();
			int hash1 = Hash(key) % M;
			while (_tables[hash1]._state != EMPTY) {
				if (_tables[hash1]._state == EXIST && _tables[hash1]._kv.first == key) {
					return &_tables[hash1];
				}
				if (hash1 == M - 1) hash1 = 0;
				else hash1++;
			}
			return nullptr;
		}
		bool Erase(const K& key) {
			int M = _tables.size();
			int hash1 = Hash(key) % M;
			while (_tables[hash1]._state != EMPTY) {
				if (_tables[hash1]._state == EXIST&&_tables[hash1]._kv.first == key) {
					_tables[hash1]._state = DELETE;
				}
				if (hash1 == M - 1) hash1 = 0;
				else hash1++;
			}
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 表中存储数据个数
	};
}


// 实现完成后，请对整形 和 字符串完成测试
int main()
{
	int a2[] = { 19,30,5,36,13,20,21,12,24,96 };
	open_address::HashTable<int, int> ht2;
	for (auto e : a2)
	{
		ht2.Insert({ e, e });
	}

	ht2.Insert({ 100, 100 });
	ht2.Insert({ 101, 101 });


	return 0;
}